/**
 * 2017年1月6日
 */
package algorithm;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author Alex
 *
 */
//支持 + - *  / ()运算
//只考虑个位数字
public class ExpressionEvaluate {
	public static String expression[] =  {
			"52+37*2+(5-10)*(2-22)+88/22",
			"6+(1+2)*5+6/2+5*9-2+7",
			"3*32*3*4",
			"5-55-5-5",
			"1+1+1+1+1",
			"1+1",
			"(5*3-6*2)*3-(1+8/2)",
			"5*(5+5*(5+(3+5)))"
	};
	public static void main(String[] args) {
		Arrays.asList(expression).forEach(x->{
			String s = "(" + x + ")";
			int cur[] = new int[]{0};
			System.out.println(eval(s,0,cur));
		});
		
	}
	//当遇到(时递归调用 ,start 是(所在的位置,end是)所在位置
	public static double eval(String exp,int start,int cur[]){
		int i = ++start;
		Stack<Integer> num = new Stack<>();
		Stack<BinaryOperator> op = new Stack<>();
		char c;
		BinaryOperator bo = null;
		int numToken = 0;
		boolean is = false;
		for(;;i++){
			if(isNum(c = gc(i,exp))){
				numToken = numToken*10 + getNum(c);
				is = true;
//				num.push(getNum(c));
			}else if(isOp(c)){
				if(is){
					num.push(numToken);
					numToken = 0;
					is=false;
				}
				
				bo = toOper(c);
				while(!op.isEmpty() && bo.prior() <= op.peek().prior()){
					int right = num.pop();
					int left = num.pop();
					BinaryOperator tbo = op.pop();
					int res = (int) tbo.eval(left, right);
					num.push(res);
				}
				op.push(bo);
			}else if(isLP(c)){
				int res = (int) eval(exp,i,cur);
				i = cur[0];
				num.push(res);
			}else if(isRP(c)){
				if(is){
					num.push(numToken);
					numToken = 0;
					is = false;
				}
				
				while(!op.isEmpty()){
					int right = num.pop();
					int left = num.pop();
					BinaryOperator tbo = op.pop();
					int res = (int)tbo.eval(left, right);
					num.push(res);
				}
				cur[0] = i;
				return num.pop();
			}
		}
	}
	//short for getChar
	public static char gc(int pos,String s){
		return s.charAt(pos);
	}
	public static boolean isNum(char c){
		return c >= '0' && c <= '9';
	}
	public static int getNum(char c){
		return c - '0';
	}
	public static boolean isLP(char c){
		return c == '(';
	}
	public static boolean isRP(char c){
		return c == ')';
	}
	public static boolean isOp(char c){
		return c == '+' || c == '-' || c == '*' || c == '/';
	}
	public static BinaryOperator toOper(char c){
		switch(c){
		case '+':
			return BinaryOperator.ADD;
		case '-':
			return BinaryOperator.MIN;
		case '*':
			return BinaryOperator.MUL;
		case '/':
			return BinaryOperator.DIV;
		default:
			return BinaryOperator.ADD;
		}
		
	}
}
/**
 * 写这类是因为想用栈实现表达式算法,Stack是范型类,不想将原生类型对应包装类当作具体参数
 * @author Alex
 */
enum BinaryOperator{
	MIN{
		public double eval(double left,double right) {
			return left - right;
		}

		public int prior() {
			return 0;
		}
	},
	ADD{
		public double eval(double left, double right) {
			return left + right;
		}
		public int prior() {
			return 0;
		}
	},
	MUL{
		public double eval(double left, double right) {
			return left * right;
		}
		public int prior() {
			return 1;
		}
	},
	DIV{
		public double eval(double left, double right) {
			return left / right;
		}
		public int prior() {
			return 1;
		}
	};
	public abstract double eval(double left,double right);
	public abstract int prior();
}
